package com.ting.test.algorithms.背包类问题;

/**
 * 01背包问题描述：
 * 有编号分别为a,b,c,d,e的N=5件物品，它们的重量w分别是2,2,6,5,4，它们的价值v分别是6,3,5,4,6，
 * 每件物品数量只有一个，现在给你个承重为M=10的背包，如何让背包里装入的物品具有最大的价值总和sum_v？
 */
public class ClassicBeiBao {
    public static void main(String[] args) {
        int[] w = new int[]{2, 2, 6, 5, 4};
        int[] v = new int[]{6, 3, 5, 4, 6};

        int sum_v = f1(w, v, 0, 10);
        System.out.println(sum_v);
    }


    /**
     * @param w     商品重量的数组
     * @param v     商品价格的数组
     * @param index 当前需要判断的商品下标
     * @param rest  当前背包剩余的承重
     * @return 在不花超的情况下，当前商品(index),以及之后的所有商品返回的总的最大价值 -1表示没有这种情况
     */
    private static int f1(int w[], int v[], int index, int rest) {
        // 超重了
        if (rest < 0) {
            return -1;//表示这种情况是不可取的
        }
        //没超重，但是 没货了
        if (index == w.length) {
            return 0;//表示商品已经装完了
        }

        //没超重 且 有货 两种情况
        //1.p1表示当前商品不装入背包的情况下，装入背包（当前商品之后的所有商品返回）的最大价值
        int p1 = f1(w, v, index + 1, rest);

        int p2 = -1;//默认情况下，-1 认为没有这种可能
        //p2 表示 将当前商品装入背包的情况下，装入背包(当前商品以及之后的所有商品)的最大价值
        int next = f1(w, v, index + 1, rest - w[index]);
        if (next != -1) {//防止超重
            p2 = v[index] + next;
        }
        return Math.max(p1, p2);


    }
}
